package com.javagi.test.sort;

/**
 * @Description 插入排序
 * 我们从 1 开始遍历每一个元素（i），然后把元素 i 插入到 0-i 里面最合适的位置，这样就排好序了。
 * @Author kuiwang
 * @Date 2020/5/29 18:15
 * @Version 1.0
 */
public class InsertSort {
    public static void main(String[] args) {
        int arr[] = {1,0,4,5,3};
        insertSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }

    public static void insertSort(int arr[]){
        //int arr[] = {1,0,4,5,3};
        int tmp, j;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i-1] > arr[i]) {
                tmp = arr[i]; //第一个位置和第二个位置比较，将比较小的数 提出来tmp
                for (j = i; j > 0; j--) {
                    if (arr[j-1] > tmp) {
                        arr[j] = arr[j-1];  //  然后将第一个位置和 tmp相比，如果第一个位置大，就将第一个位置值[大值]赋给第二个位置[小值]
                    } else {
                        break;
                    }
                }
                arr[j] = tmp;   // 最后将 tmp值[较小]赋给给第一个位置
            }
        }
    }

}